package edu.buaa.act.rtree.str

import java.lang

import edu.buaa.act.IndexEntry

import scala.collection.mutable.ArrayBuffer


class STRRTreeOneProperty(data: Array[IndexEntry], dataBlockCapacity:Int, indexBlockCapacity:Int) {
    val bData:Int = dataBlockCapacity
    val bIndex:Int = indexBlockCapacity
    val levels:ArrayBuffer[ArrayBuffer[Node]] = new ArrayBuffer[ArrayBuffer[Node]]
    val root:Node = packNode(packData(data))

    private def packData(data: Array[IndexEntry]):Array[Node] = {
        sortData(data)
        val dataLevel = new ArrayBuffer[Node]
        var i = 0
        while (i < data.length) {
            val end = if (i + bData > data.length) data.length else i + bData
            val node = new LeafNode(data.slice(i, end), dataBlockCapacity)
            dataLevel += node
            i += bData
        }
        this.levels += dataLevel
        dataLevel.toArray
    }

    private def packNode(nodes: Array[Node]):Node = {
        sortNodes(nodes)
        val upperLevelNodes = new ArrayBuffer[Node]
        var i = 0
        while (i <= nodes.length) {
            val end = if (i + bIndex > nodes.length) nodes.length else i + bIndex
            val node = new IndexNode(nodes.slice(i, end), bIndex)
            upperLevelNodes += node
            i += bIndex
        }
        if (upperLevelNodes.size > 1) {
            this.levels += upperLevelNodes
            packNode(upperLevelNodes.toArray)
        }
        else if (upperLevelNodes.size == 1) upperLevelNodes(0)
        else throw new RuntimeException("nothing to pack")
    }

    //------ utils for node(RTreeNode)---------
    private def sortNodes(data: Array[Node]): Unit = {
        nodeRecursiveSort(data, 0, data.length, 1, 3)
    }

    private def nodeRecursiveSort( data: Array[Node], left: Int, right: Int, corIndex: Int, k: Int) {
        this.stableSort(data, left, right, (o1: Node, o2: Node) => o1.compareTo(o2, corIndex))
        if(k>1) {
            val r = right - left // total entry count
            val p = r / bIndex + (if(r % bIndex == 0) 0 else 1) // total block count
            val s = lang.Math.round(Math.ceil(Math.pow(p, 1d / k))).toInt // block count at current dimension (corIndex).
            val groupLen = s * bIndex // group
            for (i <- 0 until s) {
                val start = i*groupLen+left
                val endTmp = (i+1)*groupLen+left
                val end = if(endTmp>right) right else endTmp
                if(start<end) nodeRecursiveSort(data, start, end, corIndex + 1, k - 1)
            }
        }
    }

    //------ utils for data(IndexEntry)---------
    private def sortData(data: Array[IndexEntry]): Unit = {
        dataRecursiveSort(data, 0, data.length, 1, 3)
    }

    private def dataRecursiveSort(data: Array[IndexEntry], left:Int, right:Int, corIndex:Int, k:Int) {
        this.stableSort(data, left, right, (o1: Node, o2: Node) => o1.compareTo(o2, corIndex))
        if(k>1) {
            val r = right - left; // total entry count
            val p = r / bData + (if(r % bData == 0) 0 else 1); // total block count
            val s = Math.round(Math.ceil(Math.pow(p, 1d / k))).toInt; // block count at current dimension (corIndex).
            val groupLen = s * bData; // group
            for (i <- 0 until s) {
                val start = i*groupLen+left
                val endTmp = (i+1)*groupLen+left
                val end = if(endTmp>right) right else endTmp
                if(start<end) dataRecursiveSort(data, start, end, corIndex + 1, k - 1)
            }
        }
    }

    private def stableSort[T](x: Seq[T], i: Int, j: Int, comp: (T,T) => Boolean ):Seq[T] = {
        x.take(i) ++ x.slice(i,j).sortWith(comp) ++ x.drop(i+j-1)
    }


}
